package com.zdp.algorithm.linkedlist;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 单向环形链表 --> 约瑟夫环自杀问题
 * @author Zhengdp
 * @date 2023年02月16日 13:36
 */
public class JosehpusKills {
    public static void main(String[] args) throws IOException {
        JosephusKillImpl1 impl1 = new JosephusKillImpl1();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = reader.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        Node head = new Node();
        Node p = head;
        for(int i = 1;i <= n ;i ++){
            Node cur = new Node(i);
            cur.next = p.next;
            p.next = cur;
            p = cur;
        }
        p.next = head.next;
        Node del = impl1.del(head.next, m);
        System.out.println(del.value);
    }



}

/**
 * 进阶版，在 O(N)的时间复杂度内完成
 */
class JosephusKillImpl2 {

}

// 简单版 不需要在 O(N)的时间复杂度内完成
class JosephusKillImpl1 {
    public Node del(Node head,int m) {
        int index = 1;
        Node cur = head;
        Node pre = null; // 也可以将pre指向链表的最末端 --> 因为是环状链表
        while( cur.next != cur){
            index = index % m;
            if(index == 0){
                if(pre == null){
                    cur = cur.next;
                }else{
                    pre.next = cur.next;
                    cur = pre.next;
                }
            }else{
                pre = cur;
                cur = cur.next;
            }
            index ++;
        }
        return cur;
    }
}
